4. Две окружности

Определить количество точек пересечения двух окружностей.

Вход. 6 чисел x₁, y₁, r₁, x₂, y₂, r₂, где x₁, y₁, r₁, x₂, y₂ – координаты центров окружностей, а r₁, r₂ – их радиусы. Все числа – действительные, не превышают по модулю 1000000000, заданы не более чем с 3-мя знаками после запятой.

Выход. Количество точек пересечения. Если точек пересечения бесконечно много, то вывести -1.

Пример входа	Пример выхода
0 0 5 5 0 5	2

РЕШЕНИЕ

геометрия

Анализ алгоритма

Следует рассмотреть варианты внешнего и внутреннего касания, а также возможность расположения одной окружности внутри другой. Окружности имеют бесконечное количество точек пересечения только в случае их совпадения.

Пусть dist2 = (x₂ – x₁)² + (y₂ – y₁)² – квадрат расстояния между центрами окружностей. Тогда:

· Окружности касаются извне, если (r₁ + r₂)² = dist2.

· Окружности имеют точку внутреннего касания, если (r₁ – r₂)² = dist2.

· Окружности не имеют общих точек и не содержатся друг в друге, если (r₁ + r₂)² < dist2.

· Окружности не пересекаются, но при этом содержатся одна в другой, если (r₁ – r₂)² > dist2.

Реализация алгоритма

Изначально положим, что у нас имеются две точки пересечения.

int res = 2;

Читаем входные данные.

scanf("%lf %lf %lf %lf %lf %lf",&xx1,&yy1,&r1,&xx2,&yy2,&r2);

Вычисляем квадрат расстояния между центрами окружностей.

dist2 = (xx2-xx1)*(xx2-xx1) + (yy2-yy1)*(yy2-yy1);

Проверяем, не совпадают ли окружности.

if ((xx1 == xx2) && (yy1 == yy2) && (r1 == r2)) res = -1; else

Проверяем условие внешнего касания двух окружностей.

if (fabs((r1 + r2) * (r1 + r2) - dist2) < EPS) res = 1; else

Проверяем условие внутреннего касания двух окружностей.

if (fabs((r1 - r2) * (r1 - r2) - dist2) < EPS) res = 1; else

Рассматриваем случаи, когда окружности не имеют общих точек.

if ((r1 + r2)*(r1 + r2) < dist2 - EPS) res = 0; else

if ((r1 - r2)*(r1 - r2) > dist2 + EPS) res = 0;

Выводим ответ. Если ни одно из выше перечисленных условий не выполняется, то имеем две точки пересечения.

printf("%d\n",res);